On-demand routing algorithms enable dynamic, self-starting, multihop routing between participating mobile nodes in ad hoc wireless communication networks. Various methods exist for determining a preferred on-demand route through a network. For example an ad hoc, on-demand distance vector (AODV) routing protocol allows mobile nodes to obtain routes quickly for new destinations, and does not require nodes to maintain routes to inactive destinations. Thus AODV protocols allow mobile nodes to respond to route failures and changes in network topology in a timely manner.
However, after a route is established in an on-demand routing protocol, mobile nodes generally continue using the established route until there is a need, based for example on a failure of the established route, to discover an alternative route. Therefore, even if an improved route becomes available, due for example to a change in network topology, change in link condition, or movement of one or more mobile nodes, the mobile nodes along the established route will nonetheless continue using the established route. Hence, improved routes that may become available are not utilized.
One known method for addressing the above problem is to periodically transmit route request (RREQ) packets, which explores all possible routing options in a wireless neighborhood. However, because the RREQ packets are transmitted as a broadcast, such RREQ packets can place a large overhead on wireless bandwidth. Broadcasting of RREQ packets also works against a basic principle of on-demand routing protocols, which is to conserve bandwidth by avoiding unnecessary packet transmissions.
Other known methods of route improvement in on-demand routing protocols are based on “nexthops,” which endeavor to optimize a route by minimizing a number of “hops” between nodes. These methods however risk the formation of loops. Additionally, in varying link conditions, such methods can be prone to generating RREQ packets excessively and when RREQ packets are not needed, thus unnecessarily increasing overhead on a wireless bandwidth. Furthermore, such methods risk adopting a route that is improved based on one criteria, such as node minimization, but which is inferior based on another criteria, such as route stability.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.